package oxing.util;

import java.util.Iterator;

public final class ArrayStack<E> implements Stack<E>, Iterable<E> {
	final static int MAXIMUM_CAPACITY = 1 << 30;
	int capacity;
	int limit;
	E[] arrays;

	public ArrayStack(int capacity) {
		if (capacity < 0)
			throw new IllegalArgumentException("Illegal initial capacity: " + capacity);
		capacity = capacity >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY
				: (capacity > 1) ? Integer.highestOneBit((capacity - 1) << 1) : 1;
		inflateTable(capacity);
		limit = 0;
	}

	@SuppressWarnings("unchecked")
	private E[] inflateTable(int capacity) {
		return arrays = (E[]) new Object[this.capacity = capacity];
	}

	public void push(E e) {
		if (limit == capacity)
			resize(capacity << 1);
		arrays[limit++] = e;
	}

	public E pop() {
		if (limit == 0)
			return null;
		E e = arrays[--limit];
		arrays[limit] = null;
		return e;
	}

	public E peek() {
		if (limit == 0)
			return null;
		return arrays[limit - 1];
	}

	public int size() {
		return limit;
	}

	public void clear() {
		final E[] arrays = this.arrays;
		final int length = limit;
		for (int i = 0; i < length; i++)
			arrays[i] = null;
		limit = 0;
	}

	private final void resize(int newCapacity) {
		if (capacity == MAXIMUM_CAPACITY)
			return;
		E[] oldTable = arrays;
		E[] newTable = inflateTable(newCapacity);
		System.arraycopy(oldTable, 0, newTable, 0, limit);
	}

	public Iterator<E> iterator() {
		return new ArrayIterator<E>(arrays, 0, limit);
	}

	final static class ArrayIterator<E> implements Iterator<E> {
		final E[] arrays;
		int start;
		final int end;

		public ArrayIterator(E[] arrays, int offest, int length) {
			this.arrays = arrays;
			this.end = (this.start = offest) + length;
		}

		public boolean hasNext() {
			return start < end;
		}

		public E next() {
			return start < end ? arrays[start++] : null;
		}

		public void remove() {
			throw new IteratorException("Does not support remove();");
		}
	}
}